从数组到链表(C Primer Plus 第六版) 您所在的位置:网站首页 c primer plus讲解 从数组到链表(C Primer Plus 第六版)

从数组到链表(C Primer Plus 第六版)

2023-12-30 02:33| 来源: 网络整理| 查看: 265

「这是我参与11月更文挑战的第1天,活动详情查看:2021最后一次更文挑战」。

一、从数组到链表

​ 理想的情况是用户不断的添加数据,而不是先指定要输入多少项,也不用让程序分配多余的空间。这可以通过在输入每一项后调用malloc()分配正好能存储该项的空间。如果输入3部影片,程序就调用malloc()3次;如果用户输入300部就调用300次!

​ 比较一下,一种方法是调用malloc()一次,为300个filem结构请求分配足够的空间;另一种方法是调用malloc ()300次,分别为每个file结构请求分配足够的空间。前者分配的是连续的内存块,只需要一个单独的指向struct变量(film)的指针,该指针指向已分配块中的第Ⅰ个结构。简单的数组表示法让指针访问块中的每个结构,如前面代码段所示。第⒉种方法的问题是,无法保证每次调用malloc()都能分配到连续的内存块。这意味着结构不一定被连续储存(见图17.因此,与第1种方法储存一个指向300个结构块的指针相比,你需要储存300个指针,每个指针指向一个单独储存的结构。

书里面这段话写的太好了,我全加粗了!

image-20211016202914570

​ 每次使用malloc()为新结构分配空间时,也为新指针分配空间。但是,还得需要另一个指针来跟踪新分配的指针,用于跟踪新指针的指针本身,也需要一个指针来跟踪,以此类推要重新定义结构才能解决这个潜在的问题,即每个结构中包含指向next 结构的指针。然后,当创建新结构时,可以把该结构的地址储存在上一个结构中。简而言之,可以这样定义film结构:

#define TSIZE 45 //储存片名的数组大小 struct film { char title [ TSIZE]; int rating; struct film * next; }; 1.1 重要的一个点

虽然结构不能含有与本身类型相同的结构,但是可以含有指向同类型结构的指针。这种定义是定义链表( linked list)的基础,链表中的每一项都包含着在何处能找到下一项的信息。 在学习链表的代码之前,我们先从概念上理解一个链表。假设用户输入的片名是Modern Times,等级为10。程序将为film类型的结构分配空间,把字符串 Modern Times拷贝到结构中的title成员中,然后设置rating成员为10。为了表明该结构后面没有其他结构,程序要把next成员指针设置为NULL(NULL是一个定义在stdio.h头文件中的符号常量,表示空指针)。当然,还需要一个**单独的指针储存第1个结构的地址,该指针被称为头指针( head pointer)。头指针指向链表中的第1项。**图17.2演示了这种结构(为节约图片空间,压缩了title成员中的空白)。

image-20211016205325013

​ 现在,假设用户输入第2部电影及其评级,如Midnight in Paris和8。程序为第2个film类型结构分配空间,把新结构的地址储存在第Ⅰ个结构的next成员中(擦写了之前储存在该成员中的NULL)这样链表中第Ⅰ个结构中的next 指针指向第2个结构。然后程序把Midnight in Paris和8拷贝到新结构中,并把第2个结构中的next 成员设置为NOLL,表明该结构是链表中的最后一个结构。图17.3演示这两个项。

image-20211016205755241

书上的介绍写的太好了!

每加入一部新电影,就以相同的方式来处理。新结构的地址将储存在上-一个结构中,新信息储存在新结构中,而且新结构中的next成员设置为NULL

image-20211016205854891

假设要显示这个链表,每显示一-项, 就可以根据该项中已储存的地址来定位下一个待显示的项。然而,这种方案能正常运行,还需要一个指针储存链表中第1项的地址,因为链表中没有其他项储存该项的地址。此时,头指针就派上了用场。

二、使用链表

我们用代码来实现一个链表!

#include #include #include #define TSIZE 45 struct film { char title[TSIZE]; int rating; struct film *next; //指向链表中的下一个结构 }; char *s_gets(char *st, int n); //函数返回值为char类型的指针 int main(void) { struct film *head = NULL; struct film *prev, *current; char input[TSIZE]; puts("Enter first movie title:"); while (s_gets(input, TSIZE) != NULL && input[0] != '\0') { current = (struct film *)malloc(sizeof(struct film)); if (head == NULL) head = current; else prev->next = current; current->next = NULL; strcpy(current->title, input); puts("Enter your rating :"); scanf("%d", ¤t->rating); while (getchar() != '\n') continue; puts("Enter next movie title (empty line to stop)"); prev = current; } /*显示电影列表*/ if (head == NULL) printf("No data entered. "); else printf("Here is the movie list: \n"); current = head; while (current != NULL) { printf ("Movie: %s Rating: %d\n",current->title,current -> rating); current = current->next ; } /*完成任务,释放已分配的内存*/ current = head; while (current != NULL) { current = head; head = current->next; free(current); } printf("Bye! \n"); return 0; } char *s_gets(char *st, int n) { char *ret_val; char *find; ret_val = fgets(st, n, stdin); if (ret_val) { find = strchr(st, '\n'); if (find) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val;c } 输出结果为: PS D:\Code\C\结构> cd "d:\Code\C\结构\" ; if ($?) { gcc 链表Demo01.c -o 链表Demo01 } ; if ($?) { .\链表Demo01 } Enter first movie title: Roman Holiday Enter your rating : 8 Enter next movie title (empty line to stop) Rose Enter your rating : 2 Enter next movie title (empty line to stop) Here is the movie list: Movie: Roman Holiday Rating: 8 Movie: Rose Rating: 2

该程序用链表执行两个任务。第1个任务是,构造一个链表,把用户输入的数据储存在链表中。第2个任务是,显示链表。显示链表的任务比较简单,所以我们先来讨论它。

2.1 程序解析 2.1.1显示链表

由于书上的写的太好了,我直接照抄下来给大家参考!

显示列表从设置一个指向结构的指针开始(名为current)。由于头指针(head)已经指向链表中的第一个结构,所以可以这样表示

current = head;

然后用前面章节讲的指针表示法访问结构体中的成员

printf ("Movie: %s Rating: %d\n",current->title,current -> rating);

打印之后,在把current指针指向下一个结构

current = current->next ;

完成这些之后,再重复整个过程。当显示到链表中最后一个项时,current将被置为null,因为这是链表最后一个结构中next成员的值

while (current != NULL) { //指针访问结构中的成员可以用指针.成员即可 printf ("Movie: %s Rating: %d\n",current->title,current -> rating); current = current->next ; }

遍历链表时,为何不直接使用head指针,而要重新创建一个新指针?因为用head就会改变head中的值,程序就找不到链表的开始处

2.1.2创建链表

创建链表涉及下面3步:

(1)使用malloc ()为结构分配足够的空间;

(2)储存结构的地址;

(3)把当前信息拷贝到结构中。

​ 如无必要不用创建一个结构,所以程序使用临时存储区(input数组)获取用户输入的电影名。如果用户通过键盘模拟EOF或输入一行空行,将退出下面的循环:

​ while (s gets(input,TSIZE)!= NULL && input [0] != '\0 ')

​ 如果用户进行输入,程序就分配一个结构的空间,并将其地址赋给指针变量current:current = (struct film *) malloc(sizeof(struct film) ) ;

​ 链表中第1个结构的地址应储存在指针变量head中。随后每个结构的地址应储存在其前一个结构的next成员中。因此,程序要知道它处理的是否是第1个结构。最简单的方法是在程序开始时,把 head指针初始化为NULL。然后,程序可以使用head的值进行判断:

if (head == NULL) //第1个结构 head = current; else //subsequent structures prev->next = current;

​ 在上面的代码中,指针prev指向上一次分配的结构。 ​ 接下来,必须为结构成员设置合适的值。尤其是,把next成员设置为NULL,表明当前结构是链表的最后一个结构。还要把input数组中的电影名拷贝到title成员中,而且要给rating成员提供一个值如下代码所示:

current->next = NULL; strcpy (current->title, input) ; puts ( "Enter your rating :");scanf ( "%di",¤t->rating) ;

​ 由于s_gets ()限制了只能输入TSIZE-1个字符,所以用strcpy()函数把input 数组中的字符串拷贝到title成员很安全。

​ 最后,要为下一次输入做好准备。尤其是,要设置 prev指向当前结构。因为在用户输入下一部电影且程序为新结构分配空间后,当前结构将成为新结构的上一个结构,所以程序在循环末尾这样设置该指针: ​ prev = current; ​ 程序是否能正常运行?下面是该程序的一个运行示例;

​ Enter first movie title:

​ Spirited Away

​ Enter your rating :

​ 9 ​ Enter next movie title (empty line to stop):

​ The Duelists

​ Enter your rating :

​ 8 ​ Enter next movie title (empty line to stop) :

​ Devil Dog: The Mound of Hound ​ Enter your rating : ​ 1

​ Enter next movie title (empty line to stop) : ​ Here is the movie list: ​ Movie: Spirited Away Rating: 9 ​ Movie: The Duelists Rating: 8 ​ Movie: Devil Dog: The Mound of Hound Rating: 1 ​ Bye!

2.1.3释放链表

​ 在许多环境中,程序结束时都会自动释放malloc ()分配的内存。但是,最好还是成对调用malloc() 和free()。因此,程序在清理内存时为每个已分配的结构都调用了free()函数: ​ current = head; ​ while (current != NULL) ​ { ​ current = head; ​ head = current->next; ​ free (current) ;

​ }



【本文地址】

公司简介

联系我们

今日新闻

    推荐新闻

    专题文章
      CopyRight 2018-2019 实验室设备网 版权所有